package com.chj.chuji.tijie13;

import java.util.Stack;

//https://blog.csdn.net/qq_28468707/article/details/103092052

public class Monotonousstack02 {
	public static void main(String[] args) {

		int n = 7;
		int[] arr = new int[] { 3, 4, 1, 5, 6, 2, 7 };
		int[][] res = new int[arr.length][2];

		Stack<Integer> stack = new Stack<Integer>();

		for (int j = 0; j < arr.length; j++) {
			while (!stack.empty() && arr[stack.peek()] > arr[j]) {
				int index = stack.pop();
				if (!stack.empty()) {
					res[index][0] = stack.peek();
				} else {
					res[index][0] = -1;
				}
				res[index][1] = j;
			}
			stack.add(j);
		}

		while (!stack.empty()) {
			int index = stack.pop();
			if (!stack.empty()) {
				res[index][0] = stack.peek();
			} else {
				res[index][0] = -1;
			}
			res[index][1] = -1;
		}

		for (int i = 0; i < n; i++) {
			System.out.println(res[i][0] + " " + res[i][1]);
		}

//		for i in range(n):
//		    while len(stack)>0 and arr[stack[-1]]>arr[i]:
//		        index=stack.pop(-1)
//		        if len(stack)>0:
//		            res[index][0]=stack[-1]
//		        else:
//		            res[index][0]=-1
//		 
//		        res[index][1]=i
//		    stack.append(i)
//		while len(stack)>0:
//		    index=stack.pop(-1)
//		    if len(stack)>0:
//		        res[index][0]=stack[-1]
//		    else:
//		        res[index][0]=-1
//		    res[index][1] = -1
//		for i in range(n):
//		    print (str(res[i][0])+" "+str(res[i][1]))
	}
}

//n=int(input())
//arr = list(map(int,input().split()))
//res=[[0 for _ in range(2)] for _ in range(n)]
//stack=[]
//for i in range(n):
//    while len(stack)>0 and arr[stack[-1]]>arr[i]:
//        index=stack.pop(-1)
//        if len(stack)>0:
//            res[index][0]=stack[-1]
//        else:
//            res[index][0]=-1
// 
//        res[index][1]=i
//    stack.append(i)
//while len(stack)>0:
//    index=stack.pop(-1)
//    if len(stack)>0:
//        res[index][0]=stack[-1]
//    else:
//        res[index][0]=-1
//    res[index][1] = -1
//for i in range(n):
//    print (str(res[i][0])+" "+str(res[i][1]))
